#include <iostream>
#include <vector>
#include <ctime>
#include <random>
#include <chrono>
using namespace std;

struct SkiplistNode
{
    int _val;
    vector<SkiplistNode *> _nextArr;

    SkiplistNode(int val, int level)
        : _val(val), _nextArr(level, nullptr)
    {
    }
};

class Skiplist
{
    typedef SkiplistNode Node;

private:
    Node *_head;
    size_t _maxLevel = 32;
    double _p = 0.25;

public:
    Skiplist()
    {
        srand(time(0));

        // 头节点，层数是1
        _head = new Node(-1, 1);
    }

    bool search(int target)
    {
        Node *cur = _head;
        int level = _head->_nextArr.size() - 1;
        while (level >= 0)
        {
            // 目标值比下一个节点值要大，向右走
            // 下一个节点是空(尾)，目标值比下一个节点值要小，向下走
            if (cur->_nextArr[level] && cur->_nextArr[level]->_val < target)
            {
                // 向右走
                cur = cur->_nextArr[level];
            }
            else if (cur->_nextArr[level] == nullptr || cur->_nextArr[level]->_val > target)
            {
                // 向下走
                --level;
            }
            else
            {
                return true;
            }
        }

        return false;
    }

    vector<Node *> FindPrevNode(int num)
    {
        Node *cur = _head;
        int level = _head->_nextArr.size() - 1;

        // 插入位置每一层前一个节点指针
        vector<Node *> prevV(level + 1, _head);

        while (level >= 0)
        {
            // 目标值比下一个节点值要大，向右走
            // 下一个节点是空(尾)，目标值比下一个节点值要小，向下走
            if (cur->_nextArr[level] && cur->_nextArr[level]->_val < num)
            {
                // 向右走
                cur = cur->_nextArr[level];
            }
            else if (cur->_nextArr[level] == nullptr || cur->_nextArr[level]->_val >= num)
            {
                // 更新level层前一个
                prevV[level] = cur;

                // 向下走
                --level;
            }
        }

        return prevV;
    }

    void add(int num)
    {
        vector<Node *> prevArr = FindPrevNode(num);

        int n = RandomLevel();
        Node *newnode = new Node(num, n);

        // 如果n超过当前最大的层数，那就升高一下_head的层数
        if (n > _head->_nextArr.size())
        {
            _head->_nextArr.resize(n, nullptr);
            prevArr.resize(n, _head);
        }

        // 链接前后节点
        for (size_t i = 0; i < n; ++i)
        {
            newnode->_nextArr[i] = prevArr[i]->_nextArr[i];
            prevArr[i]->_nextArr[i] = newnode;
        }
    }

    bool erase(int num)
    {
        vector<Node *> prevV = FindPrevNode(num);

        // 第一层下一个不是val，val不在表中
        if (prevV[0]->_nextArr[0] == nullptr || prevV[0]->_nextArr[0]->_val != num)
        {
            return false;
        }
        else
        {
            Node *del = prevV[0]->_nextArr[0];
            // del节点每一层的前后指针链接起来
            for (size_t i = 0; i < del->_nextArr.size(); i++)
            {
                prevV[i]->_nextArr[i] = del->_nextArr[i];
            }
            delete del;

            // 如果删除最高层节点，把头节点的层数也降一下
            int i = _head->_nextArr.size() - 1;
            while (i >= 0)
            {
                if (_head->_nextArr[i] == nullptr)
                    --i;
                else
                    break;
            }
            _head->_nextArr.resize(i + 1);

            return true;
        }
    }

    int RandomLevel()
    {
        size_t level = 1;
        // rand() ->[0, RAND_MAX]之间
        while (rand() <= RAND_MAX * _p && level < _maxLevel)
        {
            ++level;
        }

        return level;
    }
    int RandomLevel2()
    {
        // 静态随机数生成器 只会在第一次调用该函数时被初始化
        // 生成器的种子是当前时间自纪元(1970年1月1日)以来的纳秒数
        static std::default_random_engine generator(std::chrono::system_clock::now().time_since_epoch().count());
        // 静态均匀分布对象 用于生成 [0.0, 1.0) 范围内的双精度浮点数
        static std::uniform_real_distribution<double> distribution(0.0, 1.0);

        size_t level = 1;
        while (distribution(generator) <= _p && level < _maxLevel)
        {
            ++level;
        }

        return level;
    }
    void Print()
    {
        printf("--------------------------------------------------------\n");
        Node *cur = _head;
        while (cur)
        {
            printf("%d\n", cur->_val);
            // 打印每个每个cur节点
            for (auto e : cur->_nextArr)
            {
                printf("%2s ", "↓");
            }
            printf("\n");

            cur = cur->_nextArr[0];
        }
        printf("--------------------------------------------------------\n");
    }
};

// 随即层数最大值 经测试是16
// int main()
// {
//     Skiplist sl;
//     int max = 0;
//     for (size_t i = 0; i < 1000000000; ++i)
//     {
//         //cout << sl.RandomLevel() <<" ";
//         int r = sl.RandomLevel();
//         if (r > max)
//             max = r;
//     }
//     cout << max << endl;

//     return 0;
// }

// 测试std随机数生成器
// int main()
// {
// 	unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
// 	std::default_random_engine generator(seed);

// 	std::uniform_real_distribution<double> distribution(0.0, 1.0);
// 	size_t count = 0;
// 	for (int i = 0; i < 100; ++i)
// 	{
// 		if (distribution(generator) <= 0.25)
// 			++count;
// 	}
// 	cout << count << endl;// 100次有17次生成的数小于等于0.25

// 	return 0;
// }

// 测试跳表
int main()
{
    Skiplist slist;
    // int a[] = { 5, 2, 3, 8, 9, 6, 5, 2, 3, 8, 9, 6, 5, 2, 3, 8, 9, 6 };
    int a[] = {3, 7, 11, 19, 22, 26, 37};
    for (auto e : a)
    {
        slist.add(e);
    }
    slist.Print();

    int x;
    cout << "请输入要删除的元素：";
    cin >> x;
    slist.erase(x);
    slist.Print();

    cout << "请输入要查找的元素：";
    cin >> x;
    if (slist.search(x))
        cout << "找到了" << endl;
    else
        cout << "没找到" << endl;
    cout << "请输入要查找的元素：";
    cin >> x;
    if (slist.search(x))
        cout << "找到了" << endl;
    else
        cout << "没找到" << endl;

    return 0;
}